package test;

import java.util.HashMap;
import java.util.Map;

class Node {
    public int key;
    public int val;

    public Node prev;

    public Node next;

    public Node() {

    }

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", val=" + val +
                '}';
    }
}

public class MyLRUCache {
    public Node head;
    public Node tail;

    public int usedsize;
    public Map<Integer, Node> cache;
    public int capacity;

    public MyLRUCache(int capacity) {
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
        cache = new HashMap<>();
        this.capacity = capacity;
    }

    //插入元素
    public void put(int key, int val) {
        Node node = cache.get(key);
        if (node == null) {
            Node newnode = new Node(key, val);
            cache.put(key, newnode);
            addToTail(newnode);
            usedsize++;
            //检查当前双向链表的有效数据个数 是不是超过了capacity
            if (usedsize > capacity) {
                Node removeNode = removeHead();
                cache.remove(removeNode.key);
                usedsize--;
            }
            printNodes("put");
        } else {
            //更新val的值，其实没必要
            node.val = val;
            moveTotail(node);
        }
    }

    //删除指定节点
    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //移动当前节点到尾巴节点
    public void moveTotail(Node node) {
        removeNode(node);
        addToTail(node);
    }

    //添加到尾巴节点
    public void addToTail(Node node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    //删除最近没使用的头结点
    public Node removeHead() {
        Node del = head.next;
        head.next = del.next;
        del.next.prev = head;
        return del;
    }

    //访问当前的key 把你访问的节点放到尾巴
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        //把最近使用的放到了尾巴
        moveTotail(node);
        printNodes("get");
        return node.val;
    }

    public void printNodes(String str) {
        System.out.println(str + " ");
        Node cur = head.next;
        while (cur != tail) {
            System.out.print(cur + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MyLRUCache myLRUCache = new MyLRUCache(3);
        myLRUCache.put(100, 1);
        myLRUCache.put(200, 2);
        myLRUCache.put(300, 3);
        System.out.println("获取元素");
        myLRUCache.get(200);
        myLRUCache.get(100);
        System.out.println("存放元素，会删除头结点，因为头节点是最近最少使用的");
        myLRUCache.put(999, 9);
    }
}
